package 二分法;

/**
 * @author： li
 * @date： 2022-01-17 21:32
 * @version 1.0
 */

/*问题描述
　　给定平面上的n个点。你需要去删掉恰好k个点(k<n)，使得剩下的n-k个点所构成的集合的直径尽量小。
   一个点集的直径是指集合中最远点对的距离。只含一个点的集合的直径等于0。
输入格式
　　第一行包含一对整数n,k (2≤n≤1000, 1≤k≤30, k<n)——对应平面上点的个数和需要删掉的点数。
　　接下来n行描述了这些点，一个点一行。每个描述包括一对整数，xi,yi(0≤xi,yi≤32000)——第i个点的坐标。给出的点可以重合。
输出格式
　　输出k个不同的用空格隔开的整数——删除的点的标号。
　　输入中给出的点是有序的，标号为1到n。你可以用任意顺序输出这些标号。如果有多组解，输出任意一组。
样例输入
样例1
5 2
1 2
0 0
2 2
1 1
3 3
样例2
4 1
0 0
0 0
1 1
1 1
样例输出
样例1
5 2
样例2
3
数据规模和约定
　　2≤n≤1000, 1≤k≤30, k<n，0≤xi,yi≤32000
 */
import java.util.ArrayList;
import java.util.Scanner;
public class 最小直径_Mininum_Diameter_未解决 {
    static int n,k;
    static int[] x;
    static int[] y;
    static long distance=0;//点集直径的平方
    static long ans=0;
    static ArrayList<Integer> result;
    static long distance_pow(int i,int j){//返回直径的平方
        return Math.abs(x[i]-x[j])*Math.abs(x[i]-x[j])
                +Math.abs(y[i]-y[j])*Math.abs(y[i]-y[j]);
    }
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        n=sc.nextInt();
        k=sc.nextInt();
        x=new int[n+1];
        y=new int[n+1];
        result=new ArrayList<>();
        for(int i=1;i<=n;i++){
            x[i]=sc.nextInt();
            y[i]=sc.nextInt();
        }
//        System.out.println(" ");
//        for(int i=1;i<=n;i++)
//            System.out.print(y[i]+" ");
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++){
//                distance=Math.max(distance,distance_pow(i,j));
                if(distance_pow(i,j)>=distance){
                    distance=Math.max(distance,distance_pow(i,j));
                    result.add(j);
                    result.add(i);
                }
            }
//        System.out.println("点集直径最大为："+distance);
//        for(int i=1;i<=n;i++)
//            for(int j=i+1;j<=n;j++){
//               ans=distance_pow(i,j);
//               if(ans==distance){
//                   result.add(j);
//                   result.add(i);
//                   System.out.println(j+" "+i);
//               }
//            }
        for(int i:result)
            System.out.print(i+" ");
//        for(int i=result.size()-1;i>=result.size()-k;i--)
//            System.out.print(result.get(i)+" ");
    }
}
